/**
 * @file SeqList.tpp
 * @brief 顺序表类模板的实现文件
 */

/**
 * @brief 默认构造函数的实现
 * 
 * 创建一个默认容量为10的空顺序表，为数据数组分配内存空间。
 * @tparam T 顺序表中存储的元素类型
 */
template<typename T>
SeqList<T>::SeqList() {
	this->capacity = 10; // 设置默认容量
	this->data = new T[this->capacity]; // 使用方括号进行数组分配
}

/**
 * @brief 带参数构造函数的实现
 * 
 * 创建一个指定容量的空顺序表，为数据数组分配指定大小的内存空间。
 * @tparam T 顺序表中存储的元素类型
 * @param capacity 顺序表的初始容量
 */
template<typename T>
SeqList<T>::SeqList(const size_t &capacity) {
	this->capacity = capacity;
	this->data = new T[this->capacity]; // 使用方括号进行数组分配
}

/**
 * @brief 析构函数的实现
 * 
 * 释放顺序表占用的动态内存，避免内存泄漏。
 * 将数据指针置为nullptr，并重置长度为0。
 * @tparam T 顺序表中存储的元素类型
 */
template<typename T>
SeqList<T>::~SeqList() {
	delete[] data;
	this->len = 0;
}

/**
 * @brief 扩容函数的实现
 * 
 * 将顺序表的容量扩大到指定大小，复制原有元素到新分配的内存空间。
 * 新容量必须大于当前容量，否则会输出错误信息并返回。
 * @tparam T 顺序表中存储的元素类型
 * @param newCapacity 新的顺序表容量，必须大于当前容量
 */
template<typename T>
void SeqList<T>::enlarge(const size_t &newCapacity) {
	if(this->capacity >= newCapacity) { // 新容量必须大于当前容量
		cerr << "[Error] New capacity must be larger than current capacity." << endl;
		return;
	}
	T* new_data = new T[newCapacity]; // 分配新的更大的内存空间
	// 只复制有效元素，而不是整个数组
	for (size_t i = 0; i < this->len; i++) {
		new_data[i] = this->data[i];
	}
	delete[] data; // 释放旧的内存空间
	data = new_data; // 更新数据指针
	this->capacity = newCapacity; // 更新容量
}

/**
 * @brief 在尾部添加元素的实现
 * 
 * 在顺序表的末尾添加一个新元素，如果容量不足则自动扩容（扩容为原容量的两倍+1）。
 * @tparam T 顺序表中存储的元素类型
 * @param val 要添加的元素值
 */
template<typename T>
void SeqList<T>::push_back(const T &val) {
	if(this->len >= this->capacity){
		this->enlarge(2 * (this->capacity + 1)); // 使用+1确保即使capacity为0也能正常工作
	}
	this->data[this->len] = val; // 在末尾添加新元素
	++this->len; // 更新元素个数
}

/**
 * @brief 在指定位置插入元素的实现
 * 
 * 在顺序表的指定索引位置插入一个新元素。如果索引超出范围，会输出错误信息并返回。
 * 如果容量不足，则自动扩容为原容量的两倍。
 * @tparam T 顺序表中存储的元素类型
 * @param index 插入位置的索引（0 <= index <= len）
 * @param val 要插入的元素值
 */
template<typename T>
void SeqList<T>::insert(const size_t &index, const T &val) {
	//0<=index<=len 索引范围检查
	if (index < 0 || index > this->len) { 
		cerr << "[Error] Index out of range." << endl;
		return;
	}
	if(this->len >= this->capacity){
		this->enlarge(2 * this->capacity); // 容量不足时扩容
	}
	// 将插入位置后的元素向后移动一位
	for (size_t i = len; i > index; i--){ 
		this->data[i] = this->data[i-1];
	}
	this->data[index] = val; // 在指定位置插入新元素
	++len; // 更新元素个数
}

/**
 * @brief 查找元素的实现
 * 
 * 遍历顺序表，查找是否存在指定值的元素。
 * @tparam T 顺序表中存储的元素类型
 * @param val 要查找的元素值
 * @return 如果找到返回true，否则返回false
 */
template<typename T>
bool SeqList<T>::find(const T &val) {
	// 只遍历有效元素，而不是整个数组
	for (size_t i = 0; i < this->len; i++) { 
		if (this->data[i] == val){
			return true; // 找到元素，返回true
		}
	}
	return false; // 未找到元素，返回false
}

/**
 * @brief 显示所有元素的实现
 * 
 * 打印顺序表中所有元素到标准输出，元素之间用空格分隔。
 * @tparam T 顺序表中存储的元素类型
 */
template<typename T>
void SeqList<T>::show() {
	cout << "SeqList: ";
	// 只显示有效元素，而不是整个数组
	for (size_t i = 0; i < this->len; i++) { 
		cout << this->data[i] << " ";
	}
	cout << endl;
}

/**
 * @brief 获取元素个数的实现
 * 
 * @tparam T 顺序表中存储的元素类型
 * @return 当前顺序表中存储的元素个数
 */
template<typename T>
size_t SeqList<T>::getLen() const {
	return len;
}

/**
 * @brief 获取当前容量的实现
 * 
 * @tparam T 顺序表中存储的元素类型
 * @return 当前顺序表的容量
 */
template<typename T>
size_t SeqList<T>::getCapacity() const {
	return capacity;
}

/**
 * @brief 删除指定元素的实现
 * 
 * 删除顺序表中第一个值等于val的元素。如果未找到该元素，会输出错误信息并返回。
 * @tparam T 顺序表中存储的元素类型
 * @param val 要删除的元素值
 */
template<typename T>
void SeqList<T>::remove(const T &val) {
	size_t index = 0;
	// 查找要删除的元素的位置
	while(index < this->len && this->data[index] != val){
		++index;
	}
	// 如果未找到元素，输出错误信息并返回
	if(index == this->len){
		cerr << "[Error] Element not found." << endl;
		return;
	}
	// 将删除位置后的元素向前移动一位
	for (size_t i = index; i < this->len - 1; i++) {
		this->data[i] = this->data[i+1];
	}
	--this->len; // 更新元素个数
}